import java.util.Arrays;

/**
 * @author WangTianyi
 * @create 2021-12-08 22:51
 */
public class RadixSort {
    public static void main(String[] args) {
        int[] array1 = new int[]{421, 240, 115, 532, 305, 430, 124};
        radixSort(array1,3, 10);
        System.out.println(Arrays.toString(array1));
    }
    public static void radixSort(int[] array, int d, int r){//d为最高位数，r为基数
        int[] tempArray = new int[array.length];
        int[] count = new int[r]; // Java语言中，数组创建出来以后，里面的元素为默认值，int的默认值为0，因此不需要额外初始化
        int i, j, num;
        int division = 1;
        for(i=0; i<d; i++){
            for(j=0; j<array.length; j++){//通过遍历原数组，构造出count数组
                num = array[j]/division % r;
                count[num]++;
            }

            for(j=1; j<count.length; j++){//遍历计数数组，将其变为累加数组 // 初始条件j=1容易写成j=0从而下标越界
                count[j] = count[j] + count[j-1];
            }

            for(j=array.length-1; j>=0; j--){//逆序遍历原数组，构造出tempArray数组，即收集后的数组
                num = array[j]/division % r;
                tempArray[--count[num]] = array[j];
            }

            System.arraycopy(tempArray, 0, array, 0, array.length);
            Arrays.fill(count, 0);

            division*=r;//此条件一开始写的时候漏掉了
        }
    }
}
